package interview.Sorting;

public class QuickSort2 {
	private static int Partition(int[] num , int left, int right){
		int i = left;
		int j = right+1;
		
		while(true){
				while((num[++i]< num[left]))
					if(i==right)
						break;
				
				while((num[--j]>num[left]))
					if(j==left)
						break;
				
				if((i>=j))break;
				Generic.swap(num, i, j);				
			}
			Generic.swap(num,left,j);
			return j;		
	}
	
	public static void sort(int[]num,int left, int right){
		int partition;
		if(left<right){
			partition=Partition(num, left, right);			
			System.out.println("\n\nSort after the middle element " + num[partition] );
			Generic.printArray(num);
			sort(num,left,partition-1);
			sort(num,partition+1,right);
		}
	}
}
